// 快速排序：取一个数作为基准值[以中间项为基准值]，小于这个基准数的放在左边，大于基准值的放在右边，递归
function sort (arr,l,r){
    let i = l
    let j =r
    let c = Math.floor((l+r)/2)  //取中间值作为指点，比较
    console.log('c==='+c);
    let temp
    // 左右两端进行扫描，只要两端还没有交替，就一直扫描
    while(i<=j){
        // 寻找直到比支点大的数
        while(arr[i]<arr[c]){
            i++
            console.log('i====='+i);  
        }
        // 寻找直到比支点小的数
        while(arr[c]<arr[j]){
            j--
            console.log('j===='+j);
        }
        // 此时找到了比支点小的数（右边），比支点大的数（左边），将他们交换位置
        if(i<=j){
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
            i++
            j--
        }
        console.log(arr);
    }
    // “左边”再做排序，直到左边剩下一个数（递归出口）
    if(l<j){
        sort(arr,l,j)
    }
    // "右边"再做排序，直到右边剩下一个数（递归出口）
    if(i<r){
        sort(arr,i,r)
    }
    console.log(arr);
}
let arr1 = [3,2,5,7,9,4,1,6,8]
let n1 = arr1.length
sort(arr1,0,n1-1)
